public class Percolation {

    private int N;
    private boolean[][] open;
    private WeightedQuickUnionUF uf;
    private WeightedQuickUnionUF uf2;

    // create N-by-N grid, with all sites blocked
    public Percolation(int N) {
        this.open = new boolean[N][N];
        this.N = N;
        this.uf = new WeightedQuickUnionUF(N*N + 2);
        this.uf2 = new WeightedQuickUnionUF(N*N + 2);
    }

    // open site (row i, column j) if it is not already
    public void open(int i, int j) {
        if (i < 1 || i > N || j < 1 || j > N) {
            throw new IndexOutOfBoundsException();
        }
        this.open[i-1][j-1] = true;

        if (i > 1 && isOpen(i-1, j)) {
            union(i, j, i-1, j);
        }
        if (i < N && isOpen(i+1, j)) {
            union(i, j, i+1, j);
        }
        if (j > 1 && isOpen(i, j-1)) {
            union(i, j, i, j-1);
        }
        if (j < N && isOpen(i, j+1)) {
            union(i, j, i, j+1);
        }
        if (i == 1) {
            unionWithTop(i, j);
        }
        if (i == N) {
            unionWithBottom(i, j);
        }
    }

    private void union(int i1, int j1, int i2, int j2) {
        this.uf.union((i1-1)*N + j1, (i2-1)*N + j2);
        this.uf2.union((i1-1)*N + j1, (i2-1)*N + j2);
    }

    private void unionWithTop(int i1, int j1) {
        this.uf.union((i1-1)*N + j1, 0);
        this.uf2.union((i1-1)*N + j1, 0);
    }

    private void unionWithBottom(int i1, int j1) {
        this.uf.union((i1-1)*N + j1, N*N + 1);
    }

    // is site (row i, column j) open?
    public boolean isOpen(int i, int j) {
        if (i < 1 || i > N || j < 1 || j > N) {
            throw new IndexOutOfBoundsException();
        }
        return this.open[i-1][j-1];
    }

    // is site (row i, column j) full?
    public boolean isFull(int i, int j) {
        if (i < 1 || i > N || j < 1 || j > N) {
            throw new IndexOutOfBoundsException();
        }
        return this.uf2.connected(0, (i-1)*N + j);
    }

    // does the system percolate?
    public boolean percolates() {
        return this.uf.connected(0, N*N+1);
    }

}
